1. Field of the Invention
The present invention relates to the field of computer graphics. More specifically, the present invention relates to a method of and apparatus for compressing and uncompressing (or decompressing) image data in a computer system.
2. Related Art
Computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publishing, gaming, medical diagnosis, etc. In those applications, three-dimensional (3D) objects are displayed on a computer screen by using a number of polygons to represent the three-dimensional objects. In order to portray a more realistic real-world representation, texture mapping is often applied. Texture mapping refers to techniques for using two-dimensional (2D) or three-dimensional (3D) texture images, or texture maps, for adding surface details to areas or surfaces of these 3D graphical objects. For example, given a featureless solid cube and a texture map defining a wood grain pattern, texture mapping techniques may be used to map the wood grain pattern onto the cube. The resulting image is that of a cube that appears to be made of wood. In another example, vegetation and trees can be added by texture mapping to an otherwise barren terrain model in order to portray a landscape filled with vegetation and trees.
In computer systems having dedicated graphics hardware, images for use in texture mapping are typically stored in memory in the form of a collection of tiles. These tiles are addressed and managed as a virtually contiguous region of address space by a two-dimensional index (S, T). In other words, this memory management scheme treats a texture map as an array of small, contiguous tiles each including a matrix of texels. Thereby, memory management issues, such as caching, virtual-to-physical mapping, swapping, etc. are more easily executed.
In order to utilize computer resources more efficiently, computer graphics systems typically include a graphics co-processor for offloading processing burdens from the CPU of the computer system, and a texture memory for storing texture data. Moreover, in order to further accelerate the texture mapping process, a special cache memory, also known as a texture cache, may also be implemented in the computer graphics systems for providing faster access to and temporary storage of frequently used tiles of texture data. In these computer systems, the texture data is frequently transferred between these memories. The bandwidth for transferring texture data between these memories, thus, becomes a critical factor in determining the texture mapping performance of such systems. Additionally, the memories themselves are valuable resources. Therefore, it would be advantageous to store and transfer texture data in a compressed format.
The need for a method of compressing texture images also arises in computer systems without a dedicated texture cache memory. In those systems, texture images are rendered directly from the system memory. That method of rendering, however, places significant burdens on system memory bandwidth. In addition to passing texture data and other image data, the memory bus must also handle access to the system memory by the operating system and the application programs. Therefore, in order to alleviate this problem, it is would also be advantageous to store and transfer compressed texture data such that the burden on system memory bandwidth is minimized.
A further need for a method of compressing images arises in network systems. Often, a computer network has only one or at most a few network graphic machines that are capable of rendering complex images, such as three-dimensional scientific graphs or engineering drawings. It would be advantageous if these complex images could be rendered on a network graphics machine and sent in a compressed data format over the network to a user for real-time display on the users personal computer.
Conventional methods of compressing image data, however, are not suitable for compressing complex or texture images. For instance, these conventional methods introduce significant amounts of visual artifacts, such as color xe2x80x9cjaggies,xe2x80x9d in the image data. These visual artifacts, while hardly noticeable in non-3D applications, are magnified when conventionally compressed texture images are used in texture mapping. Further, conventional compression algorithms, such as the color cell compression (CCC) algorithm, make use of a color look-up table (LUT) for storing representative colors of the image. Because color LUTs can be quite large, and given the limited system memory bandwidth, the overall performance of the texture mapping process would be significantly impeded if conventional algorithms such as the CCC algorithm are used to compress texture data.
Other well known compression schemes such as the JPEG or MPEG compression schemes produce good quality compression but are mathematically complex and require considerable amounts of hardware to implement. This high hardware cost makes these schemes unsuitable for texture compression. For the network transport case, where the implementation can be in software, these other schemes are too slow to maintain interactive frame rates.
Therefore, what is needed is a method of and apparatus for compressing and uncompressing color images with minimal information loss. What is also needed is a method of and apparatus for compressing and uncompressing color images without color look-up tables. What is yet further needed is a method of and apparatus for compressing and uncompressing texture data to be used in texture mapping. For the network transfer case, what is needed is a method that can be implemented in software and still maintain interactive frame rates.
The present invention provides for a method of and apparatus for compressing and uncompressing image data. According to one embodiment of the present invention, the method of compressing a color cell comprises the steps of: defining at least four luminance levels of the color cell; generating at least two bitmasks for the color cell, generating a first base color representative of pixels associated with a first one of the luminance levels; generating a second base color representative of pixels associated with a second one of the luminance levels; and storing the bitmasks in association with the first base color and the second base color. According to the present embodiment, the bitmasks each includes a plurality of entries each corresponding to a respective one of the pixels. Further, each entry is for storing data that identifies the luminance levels associated with the pixels. The present invention is particularly applicable to compress texture data such that the texture data can be more efficiently cached and moved during texture mapping.
In accordance with the present embodiment, the step of defining the luminance levels includes the steps of: calculating a mean luminance value for all pixels within the color cell; calculating an upper-mean luminance value for pixels having luminance values higher than the mean luminance value; and calculating a lower-mean luminance value for pixels having luminance values lower than the mean luminance value. In the present embodiment, the mean luminance value, the upper-mean luminance value, and the lower-mean luminance value partition the plurality of pixels into four different luminance levels including a highest luminance level, a high luminance level, a low luminance level, and a lowest luminance level. According to one embodiment, the first base color is computed by averaging the color values of all the pixels associated with the highest luminance level, and the second average color is computed by averaging the color values of all the pixels associated with the lowest luminance level.
In a second embodiment of the present invention, the method of compressing a color cell comprises the steps of: determining a luminance value (Y) for each pixel of the color cell; selecting a maximum luminance value (YMAX) and a minimum luminance value (YMIN) for the color cell; subdividing the interval YMAX to YMIN into at least two approximately equal subintervals; generating at least one bitmask that associates each pixel of the color cell with one subinterval; and determining an average color value for each subinterval from the pixels of the color cell associated with the subinterval.
In an example of this second embodiment, the step subdividing the interval YMAX to YMIN into at least two approximately equal subintervals comprises the step of subdividing the interval YMAX to YMIN into two approximately equal subintervals. In this example embodiment, a first subinterval is defined as YMAX to 0.5(YMAX+YMIN) and a second subinterval is defined as 0.5(YMAX+YMIN) to YMIN. In another example of this embodiment, the interval YMAX to YMIN is subdivided into four approximately equal subintervals: YMAX to 0.25(3YMAX+YMIN), 0.25(3YMAX+YMIN) to 0.5(YMAX+YMIN), 0.5(YMAX+YMIN) to 0.25(YMAX+3YMIN); and 0.25(YMAX+3YMIN) to YMIN.
In still another embodiment of the present invention, the methods of the present invention are implemented using a distributed graphic system. The distributed graphics system comprising means for compressing color cells for transmission over a network and means for decoding received compressed color cell for display by a computer. A graphics machine of this embodiment comprises both means for rendering an image and means for dividing the rendered image into color cells.
In one particular embodiment, the color cell includes a matrix of 4xc3x974 pixels, the bitmasks include thirty-two bits and each of the base colors includes sixteen bits such that a compression ratio of four bits per pixel is achieved. In that embodiment, the present invention can be modified to support the compression of luminance, intensity and alpha textures.
In furtherance of one embodiment of the present invention, the method of restoring compressed image data comprises the steps of reading at least two base colors from the compressed image data; generating at least two additional colors from the base colors; and reconstructing the color cell based on the bitmasks and the base colors and the additional colors. In one embodiment, the color cell is reconstructed by assigning each pixel one of the colors according to the pixel""s luminance level.
Embodiments of the present invention include the above and further include a computer readable memory for storing compressed texture data which comprises at least two bitmasks each having a plurality of entries each corresponding to a texel of a texture map, each of the entries for storing data identifying one of at least four luminance levels associated with a corresponding one of the texels; a first color of texels associated with a first one of the luminance levels; and a second color of texels associated with a second one of the luminance levels, wherein the bitmasks, the first color value and the second color value are for being retrieved by a computer system to reconstruct the uncompressed color cell from the compressed texture data during texturemapping.